import BinarySearchTree.TreeNode;
import LinkList.ListNode;

import java.util.*;

public class Test {
    public static  void main1(String[] args) {
        TreeNode n1 = new TreeNode(3);
        TreeNode n2 = new TreeNode(1);
        TreeNode n3 = new TreeNode(4);
        TreeNode n4 = new TreeNode(2);
        n1.left = n2;
        n1.right = n3;
        n2.right = n4;
        int x = kthLargest(n1,1);
        System.out.println(x);
    }
    public static int count;
    public static int kthLargest(TreeNode root, int k) {
        calculateCount(root);
        k = count - k + 1;
        Stack<TreeNode> stack  = new Stack<>();
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            if(--k == 0) {
                return root.val;
            }
            //如果root得到右边为空那么此时栈顶的结点一定是最小的
            root = root.right;
        }
        return -1;
    }
    public static void calculateCount(TreeNode root) {
        if(root == null) {
            return;
        }
        count++;
        calculateCount(root.left);
        calculateCount(root.right);
    }



    public static void main2(String[] args) {
        ListNode head = new ListNode(1);
        ListNode n1 = new ListNode(2);
//        ListNode n2 = new ListNode(3);
//        ListNode n3 = new ListNode(4);
//        ListNode n4 = new ListNode(5);
        head.next = n1;
        n1.next = null;
//        n2.next = n3;
//        n3.next = n4;
//        n4.next = null;
        ListNode node = new Test().reverseKGroup(head,2);
        while (node != null) {
            System.out.println(node.data);
            node = node.next;
        }
    }
    public ListNode reverseKGroup(ListNode head, int k) {
        if(k == 1) {
            return head;
        }
        ListNode cur = head;
        //这道题最重要的将链表分完组之后,不知道该如何链接,可以使用递归或者放入栈来实现
        Stack<ListNode> stack = new Stack<>();
        while (head != null) {
            int count = k;
            while (cur != null && count-- != 0) {
                cur = cur.next;
            }
            if(cur == null) {
                stack.push(head);
                break;
            }
            ListNode newhead = reverseList(head,cur);
            //旧的头结点经过翻转变为了尾结点
            stack.push(newhead);
            stack.push(head);
            head = cur;
        }
        return linkList(stack);
    }
    private ListNode linkList(Stack<ListNode> stack) {
        ListNode newhead = null;
        //这里先弹出的是头结点,后弹出的是尾结点,直接进行链接即可
        while (!stack.isEmpty()) {
            newhead = stack.pop();
            //如果是奇数个结点
            if(stack.isEmpty()) {
                return newhead;
            }
            ListNode tail = stack.pop();
            tail.next = newhead;
        }
        return newhead;
    }

    public ListNode reverseList(ListNode head,ListNode tail) {
        ListNode cur = head;
        ListNode prev = null;
        while (cur != tail) {
            ListNode curNext = cur.next;
            cur.next = prev;
            prev = cur;
            cur = curNext;
        }
        return prev;
    }

    public static TreeNode merge(TreeNode p,TreeNode q) {
        if(p == null && q == null) return null;
        if(p == null || q == null) return new TreeNode((p == null) ? q.val : p.val);
        else return new TreeNode(p.val + q.val);
    }
    public int[] solve (int[] preOrder, int[] inOrder) {
        TreeNode root = buildTree(preOrder, inOrder);
        int index = 0;
        Queue<TreeNode> queueleft = new LinkedList<>();
        Queue<TreeNode> queueright = new LinkedList<>();
        queueleft.offer(root);
        while (!queueleft.isEmpty()) {
            int size = queueleft.size();
            TreeNode cur = null;
            while (size-- > 0) {
                cur = queueleft.poll();
                if (cur.left != null) {
                    queueleft.offer(cur.left);
                }
                if (cur.right != null) {
                    queueleft.offer(cur.right);
                }
            }
            if(size == -1) {
                queueright.offer(cur);
            }
        }
        int[] a = new int[queueright.size()];
        while (!queueright.isEmpty()) {
            a[index++] = queueright.poll().val;
        }
        return a;
    }
    private TreeNode buildTree(int[] preOrder,int[] inOrder) {
        return buildTreeChild(preOrder,inOrder,0,inOrder.length-1);
    }
    private int i;
    private TreeNode buildTreeChild(int[] preOrder,int[] inOrder,int begin,int end) {
        if(begin > end) return null;
        TreeNode root = new TreeNode(preOrder[i]);
        int index = findIndex(preOrder[i],inOrder,begin,end);
        i++;
        root.left = buildTreeChild(preOrder,inOrder,begin,index-1);
        root.right = buildTreeChild(preOrder,inOrder,index+1,end);
        return root;
    }
    private int findIndex(int target,int[] inOrder,int begin,int end) {
        for(int i = begin;i <= end;i++) {
            if(inOrder[i] == target) {
                return i;
            }
        }
        return -1;
    }

    public static void main3(String[] args) {
        int[] a = new Test().solve(new int[]{1,2,4,5,6,3},new int[]{5,4,6,2,1,3});
        System.out.println(Arrays.toString(a));
    }
    public static boolean hasPathSum (TreeNode root, int sum) {
        if(root == null) return false;
        if(root.left == null && root.right == null && sum ==0) return false;
        boolean flg = calculateSum(root,0,sum) == sum;
        System.out.println(flg);
        return flg;
    }
    public static int calculateSum (TreeNode root,int sum,int target) {
        if(root == null) return -1;
        int prevSum = sum + root.val;
        if(root.left == null && root.right == null) return prevSum;
        int sumleft = calculateSum(root.left,prevSum,target);
        if(sumleft == target) return target;
        int sumright = calculateSum(root.right,prevSum,target);
        if(sumright == target) return target;
        return -1;
    }

    public static void main(String[] args) {
        TreeNode n1 = new TreeNode(1);
        TreeNode n2 = new TreeNode(-2);
        TreeNode n3 = new TreeNode(-3);
        TreeNode n4 = new TreeNode(1);
        TreeNode n5 = new TreeNode(3);
        TreeNode n6 = new TreeNode(-2);
        TreeNode n7 = new TreeNode(-1);
        n1.left = n2;
        n1.right = n3;
        n2.left = n4;
        n2.right = n5;
        n3.left = n6;
        n4.left = n7;
        System.out.println(hasPathSum(n1, -1));
    }
}